package _18_剑指OfferII;

import java.util.*;

public class _063_剑指OfferII替换单词 {

    private Node first = new Node();

    // 前缀树实现
    public String replaceWords(List<String> dictionary, String sentence) {
        for (String s : dictionary) {
            insert(s);
        }

        String[] strings = sentence.split(" ");
        for (int i = 0; i < strings.length; ++i) {
            String node = node(strings[i]);
            if (!"".equals(node)) {
                strings[i] = node;
            }
        }


        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < strings.length; ++i) {
            sb.append(strings[i]);
            if (i < strings.length) sb.append(" ");
        }
        return sb.toString();
    }

    private void insert(String word) {
        Node node = first;
        int len = word.length();
        for (int i = 0; i < len; ++i) {
            char cur = word.charAt(i);
            Node[] children = node.children;
            if (children == null) children = node.children = new Node[26];
            Node child = children[cur - 'a'];
            if (child != null) {
                node = child;
                continue;
            }
            Node newNode = new Node();
            // 新建
            children[cur - 'a'] = newNode;
            node = newNode;
        }
        node.isWord = true;
    }

    private String node(String word) {
        StringBuilder sb = new StringBuilder();
        Node node = first;
        int len = word.length();
        for (int i = 0; i < len; ++i) {
            if (node.isWord) break;
            char cur = word.charAt(i);
            Node[] children = node.children;
            Node child = children[cur - 'a'];
            if (child != null) {
                sb.append(cur);
                node = child;
                continue;
            }
            return "";
        }
        return sb.toString();
    }

    static class Node {

        Node[] children;

        boolean isWord;
    }

    // 通过HashMap查询实现
    public String replaceWords1(List<String> dictionary, String sentence) {
        // HashMap实现前缀数替换
        Set<String> prefixContainers = new HashSet<>(dictionary);
        int len = sentence.length();
        int left = 0;
        StringBuilder sb = new StringBuilder();
        for (int right = 0; right < len; ++right) {
            String subStr = sentence.substring(left, right + 1);
            if (sentence.charAt(right) == ' ' || right == len - 1) {
                sb.append(subStr);
                left = right + 1;
                continue;
            }
            if (prefixContainers.contains(subStr)) {
                // 找到替换的字符串
                sb.append(subStr).append(' ');
                // 直接跳到下一个字符串
                while (right < len && sentence.charAt(right) != ' ') {
                    right++;
                }
                left = right + 1;
            }
        }
        if (sb.charAt(sb.length() - 1) == ' ') {
            sb.delete(sb.length() - 1, sb.length());
        }

        return sb.toString();
    }

}
